package com.shm.leetcode;
/**
 * @author: shm
 * @dateTime: 2020/11/19 10:49
 * @description: 283. 移动零
 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 *
 * 示例:
 *
 * 输入: [0,1,0,3,12]
 * 输出: [1,3,12,0,0]
 * 说明:
 *
 * 必须在原数组上操作，不能拷贝额外的数组。
 * 尽量减少操作次数。
 */
public class MoveZeroes {
    public void moveZeroes(int[] nums) {
        int n = nums.length;

        int cnt=0;
        for (int i = n-1; i >=0; i--) {
            while(i>=0&&nums[i]!=0){
                i--;
            }
            if (i<0){
                break;
            }
            if(nums[i]==0){
                cnt++;
                for(int j=i;j<n-cnt;j++){
                    int tmp = nums[j];
                    nums[j]=nums[j+1];
                    nums[j+1]=tmp;
                }
            }
        }
    }

    public void moveZeroes_2(int[] nums) {
        int n = nums.length;
        for (int i = 1; i < n; i++) {
            int j = i-1;
            while (j>=0&&nums[j]==0){
                int tmp = nums[j+1];
                nums[j+1] = nums[j];
                nums[j]=tmp;
                j--;
            }
        }
    }

    /***
     * 遍历数组，把不是0的一直往前放
     * @param nums
     */
    public void moveZeroes2(int[] nums) {
        int j=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=0){
                int temp=nums[j];
                nums[j++]=nums[i];
                nums[i]=temp;
            }
        }

    }

    /***
     * 都知道是0，还换啥？覆盖，后面补0就行了
     * @param nums
     */
    public void moveZeroes_3(int[] nums) {
        int indexNow = 0;
        int indexNum = 0;
        int m = nums.length;

        while(indexNum<m){
            if(nums[indexNum] != 0) {
                nums[indexNow++] = nums[indexNum];
            }
            ++indexNum;
        }

        for(int i = indexNow; i < m; i++){
            nums[i] = 0;
        }
    }


    /***
     * 方法一：双指针
     * 思路及解法
     *
     * 使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。
     *
     * 右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。
     *
     * 注意到以下性质：
     *
     * 左指针左边均为非零数；
     *
     * 右指针左边直到左指针处均为零。
     *
     * 因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。
     *
     * 复杂度分析
     *
     * 时间复杂度：O(n)O(n)，其中 nn 为序列长度。每个位置至多被遍历两次。
     *
     * 空间复杂度：O(1)O(1)。只需要常数的空间存放若干变量。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/move-zeroes/solution/yi-dong-ling-by-leetcode-solution/
     * @param nums
     */
    public void moveZeroes_4(int[] nums) {
        int n = nums.length, left = 0, right = 0;
        while (right < n) {
            if (nums[right] != 0) {
                swap(nums, left, right);
                left++;
            }
            right++;
        }
    }

    public void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}
